def bubble_sort(arr):
    """
    冒泡排序基础版本
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n):

        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1], arr[j]


    return arr




def bubble_sort_optimized(arr):
    """
    冒泡排序优化版本（添加交换标志）
    :param arr:待排序的列表
    :return:排序后的列表
    """
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True

        if not swapped:
            break
        return arr


def selection_sort(arr):
    """
    选则排序基础版本
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n):

        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr




def selection_sort_optimized(arr):
    """
    选择排序优化版本(同时找最小和最大元素)
    :param arr: 待排序的列表
    :return: 排序的列表
    """
    n = len(arr)
    for i in range(n//2):
        min_idx = i, i
        for j in range(i, n-1):
            if arr[j] < arr[min_idx]:
                min_idx = j
            if arr[j] > arr[min_idx]:
                max_idx = j


        arr[i], arr[min_idx] = arr[min_idx], arr[i]

        if max_idx == i:
            max_idx = min_idx

        arr[n-i-1], arr[max_idx] = arr[max_idx], arr[n-i-1]
    return arr



def selection_sort_optimized(arr):
    """
    选择排序优化版本（同时找最小和最大元素）
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n//2):
        min_idx = i, i
        for j in range(i, n-1):
            if arr[j] < arr[min_idx]:
                min_idx = j
            if arr[j] > arr[max_idx]:
                max_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

        if max_idx == i:
            max_idx = min_idx

        arr[n-i-1],arr[max_idx] = arr[max_idx], arr[n-i-1]
    return arr



def selection_sort_optimized(arr):
    """
    选择排序优化版本（同时找最小和最大元素）
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n//2):
        min_idx = i, i
        for j in range(i, n-i):
            if arr[j] < arr[min_idx]:
                min_idx = j
            if arr[j] > arr[min_idx]:
                max_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

        if max_idx == i:
            max_idx = min_idx
        arr[n-i-1], arr[max_idx] = arr[max_idx], arr[n-i-1]
    return arr

import time
import random


def tet_sort_algorithm(sort_func, arr_size=1000):
    """
    测试排序算法的性能
    :param sort_func: 排序函数
    :param arr_size: 测试数组大小
    """
    test_data = [random.randint(0,10000) for i in range(arr_size)]
    data_copy = test_data.copy()

    print(f"\n测试 {sort_func.__name__} (数组大小： {arr_size})")
    start_time = time.perf_counter()
    sorted_data = sort_func(data_copy)
    end_time = time.perf_counter()


    is_sorted = all(sorted_data[i] <= sorted_data[i + 1] for i in range(len(sorted_data) - 1))

    print(f"排序耗时： {end_time - start_time:.6f}秒")
    print(f"排序验证： {'成功' if is_sorted else ' 失败'}")



small_data = [5, 3, 8, 3, 2]
print("原始数据：", small_data)
print("冒泡排序结果：", bubble_sort(small_data.copy()))
print("优化冒泡排序结果:", bubble_sort_optimized(small_data.copy()))
print("选择排序结果:", selection_sort(small_data.copy()))
print("优化选择排序结果:", selection_sort_optimized(small_data.copy()))













